import sun.misc.LRUCache;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class MyLRUCache {
    static class DLinkedNode{
        public int key;
        public int val;
        public DLinkedNode prev;
        public DLinkedNode next;

        public DLinkedNode(){

        }

        public DLinkedNode(int key, int val){
            this.key = key;
            this.val = val;
        }
    }

    public DLinkedNode head;
    public DLinkedNode tail;
    public int usedSize;
    public Map<Integer, DLinkedNode> cache;
    public int capacity;

    public MyLRUCache(int capacity){
        this.head = new DLinkedNode();
        this.tail = new DLinkedNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
        cache = new HashMap<>();
        this.capacity = capacity;
        this.usedSize = 0;
    }

    public void put(int key, int val){
        // 1. 插入的时候要判断节点是否已经存在
        DLinkedNode node = cache.getOrDefault(key, null);

        if(node == null){
            // 3. 如果不存在，就插入哈希表
            DLinkedNode cur = new DLinkedNode(key, val);
            cache.put(key, cur);
            // 4. 将它放在队尾
            addToTail(cur);
            this.usedSize++;
            // 5. 判断容量是否超了
            if(usedSize > capacity){
                // 6. 删除头结点
                DLinkedNode t = removeHead();
                cache.remove(t.key);
            }
        }else{
            // 2. 如果存在，就要更新对应 key 的值
            node.val = val;
            moveToTail(node);
        }
    }

    public int get(int key){
        DLinkedNode node = cache.get(key);

        if(node == null){
            return -1;
        }

        moveToTail(node);
        return node.val;
    }

    private void addToTail(DLinkedNode node){
        DLinkedNode prev = this.tail.prev;
        prev.next = node;
        node.prev = prev;
        node.next = this.tail;
        this.tail.prev = node;
    }

    private DLinkedNode removeHead(){
        DLinkedNode dLinkedNode = this.head.next;
        DLinkedNode next = dLinkedNode.next;

        this.head.next = next;
        next.prev = this.head;

        return dLinkedNode;
    }

    private void moveToTail(DLinkedNode node){
        remove(node);

        addToTail(node);
    }

    private void remove(DLinkedNode node){
        DLinkedNode prev = node.prev;
        DLinkedNode next = node.next;

        prev.next = next;
        next.prev = prev;
    }

    public void display(){
        DLinkedNode cur = this.head.next;
        while(cur != this.tail){
            System.out.print("{" + cur.key + ", " + cur.val + "} ");
            cur = cur.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        MyLRUCache myLRUCache = new MyLRUCache(3);

        myLRUCache.put(1, 99);
        myLRUCache.display();
        myLRUCache.put(2, 89);
        myLRUCache.display();
        myLRUCache.put(3, 79);
        myLRUCache.display();

        myLRUCache.get(1);
        myLRUCache.display();
        myLRUCache.get(2);
        myLRUCache.display();

        myLRUCache.put(4, 66);
        myLRUCache.display();

        myLRUCache.put(5, 55);
        myLRUCache.display();

        myLRUCache.get(1);
        myLRUCache.display();
    }
}
